// Copyright 2023 Peppa He, Juice. All rights reserved.
#include <algorithm>
#include <cstring>
#include <fstream>
#include <iostream>
#include <random>
#include <sstream>
#include <vector>

using std::cout;
using std::endl;
using std::mt19937;
using std::random_device;
using std::uniform_int_distribution;
using std::vector;
using std::ofstream;
using std::ifstream;
using std::string;
using std::stoi;

const int SIZE = 9;
const int EMPTY = 0;
const char EMPTY_CHAR = '$';

bool isValid(const vector<vector<int>>& board, int row, int col, int num) {
  // 检查行是否合法
  for (int c = 0; c < SIZE; ++c) {
    if (board[row][c] == num) {
      return false;
    }
  }

  // 检查列是否合法
  for (int r = 0; r < SIZE; ++r) {
    if (board[r][col] == num) {
      return false;
    }
  }

  // 检查九宫格是否合法
  int startRow = 3 * (row / 3);
  int startCol = 3 * (col / 3);
  for (int r = 0; r < 3; ++r) {
    for (int c = 0; c < 3; ++c) {
      if (board[startRow + r][startCol + c] == num) {
        return false;
      }
    }
  }

  return true;
}

// 可以产生可以解，产生的话初始全部都是空，直接产生合法局面，解的话遇空则递归
bool solveSudoku(vector<vector<int>>& board) {
  for (int r = 0; r < SIZE; ++r) {
    for (int c = 0; c < SIZE; ++c) {
      if (board[r][c] == EMPTY) {
        vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        random_device rd;
        mt19937 gen(rd());
        shuffle(nums.begin(), nums.end(), gen);  // 洗牌

        for (int num : nums) {
          if (isValid(board, r, c, num)) {
            board[r][c] = num;
            if (solveSudoku(board)) {
              return true;
            }
            board[r][c] = EMPTY;  // 恢复现场
          }
        }
        return false;
      }
    }
  }
  return true;
}

// 检查解的唯一性
bool checkSolution(vector<vector<int>>& board, int& solutionCount) {
  for (int row = 0; row < SIZE; row++) {
    for (int col = 0; col < SIZE; col++) {
      if (board[row][col] == EMPTY) {
        for (int num = 1; num <= SIZE; num++) {
          if (isValid(board, row, col, num)) {
            board[row][col] = num;
            // 递归填写下一个空格
            if (checkSolution(board, solutionCount)) {
              // 如果找到了唯一解，直接返回
              if (solutionCount > 1) {
                return true;
              }
            }

            board[row][col] = EMPTY;  // 回溯
          }
        }

        return false;  // 所有可行解都已尝试过
      }
    }
  }

  solutionCount++;           // 填入最后一个空格，计数器加1
  return solutionCount > 1;  // 如果解的个数大于1，则不唯一
}

// 产生空格(默认方式)
void generateBlankCells(vector<vector<int>>& board, int numBlanks) {
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(0, SIZE - 1);  // 随机选择挖空的位置

  int blanksCount = 0;
  while (blanksCount < numBlanks) {
    int row = dis(gen);
    int col = dis(gen);
    if (board[row][col] != EMPTY) {
      board[row][col] = EMPTY;
      blanksCount++;
    }
  }
}

// 产生空格(简单难度)，无需指定空格数目
void generateBlankCellsEasy(vector<vector<int>>& board) {
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(2, 3);  // 每行随机生成2~3个空白格

  for (int r = 0; r < SIZE; ++r) {
    int numBlanks = dis(gen);
    int blanksCount = 0;
    while (blanksCount < numBlanks) {
      int col = gen() % SIZE;
      if (board[r][col] != EMPTY) {
        board[r][col] = EMPTY;
        blanksCount++;
      }
    }
  }
}

// 产生空格(中等难度)，无需指定空格数目，每行产生3-4个空格
void generateBlankCellsMedium(vector<vector<int>>& board) {
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(3, 4);  // 每行随机生成3~4个空白格

  for (int r = 0; r < SIZE; ++r) {
    int numBlanks = dis(gen);
    int blanksCount = 0;
    while (blanksCount < numBlanks) {
      int col = gen() % SIZE;
      if (board[r][col] != EMPTY) {
        board[r][col] = EMPTY;
        blanksCount++;
      }
    }
  }
}

// 产生空格(高级难度)，无需指定空格数目，7*7产生40个
void generateBlankCellsHard(vector<vector<int>>& board) {
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(1, 7);  // 随机选择挖空的位置

  int blanksCount = 0;
  while (blanksCount < 40) {
    int row = dis(gen);  // 选择中间的 7x7 区域
    int col = dis(gen);
    if (board[row][col] != EMPTY) {
      board[row][col] = EMPTY;
      blanksCount++;
    }
  }
}

// 将数独写入文件
void writeSudokuToFile(const vector<vector<int>>& board, ofstream& file) {
  for (const auto& row : board) {
    for (int num : row) {
      if (num != EMPTY) {
        file << num << " ";
      } else {
        file << EMPTY_CHAR << " ";
      }
    }
    file << endl;
  }
  file << endl;  // 空一行
}

// 解数独写入文件，并调用solve求解
void writeSolutionToFile(const vector<vector<int>>& board, ofstream& file) {
  file << "数独局面：" << endl;
  writeSudokuToFile(board, file);
  file << "解：" << endl;
  vector<vector<int>> solvedBoard = board;
  if (solveSudoku(solvedBoard)) {
    writeSudokuToFile(solvedBoard, file);
  } else {
    file << "数独无解" << endl;
  }
  file << endl;  // 空一行
}

// 读取数独，文件是字符形式，我们需要转成数字具体处理
bool readSudokuFromFile(vector<vector<int>>& board, ifstream& file) {
  for (int r = 0; r < SIZE; ++r) {
    for (int c = 0; c < SIZE; ++c) {
      char ch;
      file >> ch;
      if (ch == EMPTY_CHAR) {
        board[r][c] = EMPTY;
      } else {
        board[r][c] = ch - '0';
      }
    }
  }
  string emptyLine;
  getline(file, emptyLine);  // 读取空行
  return true;
}

// 产生合法数独终局，本质上就是调用solve，我写的solve能创造终局也能解数独
void generateSudoku(int numGames) {
  ofstream sudokuFile("legal_sudoku.txt");

  if (sudokuFile.is_open()) {
    random_device rd;
    mt19937 gen(rd());

    for (int game = 0; game < numGames; ++game) {
      vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

      solveSudoku(sudoku);
      writeSudokuToFile(sudoku, sudokuFile);
    }

    sudokuFile.close();

    cout << "已成功生成数独终局并写入文件" << endl;
  } else {
    cout << "无法打开文件" << endl;
  }
}

// 产生唯一解数独
void generateUniqueSudokuWithBlanks(int numGames, int numBlanks) {
  ofstream sudokuFile("game.txt");

  if (sudokuFile.is_open()) {
    random_device rd;
    mt19937 gen(rd());

    int gamesCount = 0;
    while (gamesCount < numGames) {
      vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

      solveSudoku(sudoku);

      generateBlankCells(sudoku, numBlanks);
      vector<vector<int>> backup = sudoku;  // 备份当前生成的数独游戏

      int solutionCount = 0;
      checkSolution(sudoku, solutionCount);

      if (solutionCount != 1) {
        continue;  // 生成的数独无唯一解，重新生成
      }

      gamesCount++;

      if (gamesCount != numGames) {
        // 用备份的进行上传，因为sudoku已经被填空了
        writeSudokuToFile(backup, sudokuFile);
        sudokuFile << endl;  // 空一行
      } else {
        // 写入最后一个局面，但不加入空行
        for (int r = 0; r < SIZE; ++r) {
          for (int c = 0; c < SIZE; ++c) {
            int num = backup[r][c];
            if (num != EMPTY) {
              sudokuFile << num << " ";
            } else {
              sudokuFile << EMPTY_CHAR << " ";
            }
          }
          if (r != SIZE - 1) sudokuFile << endl;
        }
      }
    }

    sudokuFile.close();

    cout << "已成功生成具有唯一解的数独局面并写入文件" << endl;
  } else {
    cout << "无法打开文件" << endl;
  }
}

// 用于求解数独，承接read和write，读取局面以后，求解交给write函数
void solveSudokuFromFile(const string& inputFile, const string& outputFile) {
  ifstream sudokuFile(inputFile);
  ofstream solutionFile(outputFile);

  if (sudokuFile.is_open() && solutionFile.is_open()) {
    int game = 1;
    while (!sudokuFile.eof()) {
      vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));
      readSudokuFromFile(sudoku, sudokuFile);

      solutionFile << "数独局面 " << game << ":" << endl;
      writeSolutionToFile(sudoku, solutionFile);

      ++game;
    }

    sudokuFile.close();
    solutionFile.close();

    cout << "数独解已成功写入文件" << endl;
  } else {
    cout << "无法打开文件" << endl;
  }
}

// 产生带空格的数独(默认情形下)，写入game.txt中
void generateSudokuWithBlanks(int numGames, int numBlanks) {
  ofstream sudokuFile("game.txt");

  if (sudokuFile.is_open()) {
    random_device rd;
    mt19937 gen(rd());

    for (int game = 0; game < numGames - 1; ++game) {
      vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

      solveSudoku(sudoku);
      generateBlankCells(sudoku, numBlanks);

      writeSudokuToFile(sudoku, sudokuFile);
      sudokuFile << endl;  // 空一行
    }

    // 处理最后一个局面
    vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));
    solveSudoku(sudoku);
    generateBlankCells(sudoku, numBlanks);

    // 写入最后一个局面，但不加入空行
    for (int r = 0; r < SIZE; ++r) {
      for (int c = 0; c < SIZE; ++c) {
        int num = sudoku[r][c];
        if (num != EMPTY) {
          sudokuFile << num << " ";
        } else {
          sudokuFile << EMPTY_CHAR << " ";
        }
      }
      if (r != SIZE - 1) sudokuFile << endl;
    }

    sudokuFile.close();

    cout << "已成功生成带空白格的数独局面并写入文件" << endl;
  } else {
    cout << "无法打开文件" << endl;
  }
}

// 产生带空格的数独——简单，写入game.txt中
void generateSudokuWithBlanks_Easy(int numGames) {
  ofstream sudokuFile("game.txt");

  if (sudokuFile.is_open()) {
    random_device rd;
    mt19937 gen(rd());

    for (int game = 0; game < numGames - 1; ++game) {
      vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

      solveSudoku(sudoku);
      // 调用简单版
      generateBlankCellsEasy(sudoku);

      writeSudokuToFile(sudoku, sudokuFile);
      sudokuFile << endl;  // 空一行
    }

    // 处理最后一个局面
    vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));
    solveSudoku(sudoku);
    // 调用简单版
    generateBlankCellsEasy(sudoku);

    // 写入最后一个局面，但不加入空行
    for (int r = 0; r < SIZE; ++r) {
      for (int c = 0; c < SIZE; ++c) {
        int num = sudoku[r][c];
        if (num != EMPTY) {
          sudokuFile << num << " ";
        } else {
          sudokuFile << EMPTY_CHAR << " ";
        }
      }
      if (r != SIZE - 1) sudokuFile << endl;
    }

    sudokuFile.close();

    cout << "已成功生成简单难度的数独局面并写入文件" << endl;
  } else {
    cout << "无法打开文件" << endl;
  }
}

// 产生带空格的数独——中等，写入game.txt中
void generateSudokuWithBlanks_Medium(int numGames) {
  ofstream sudokuFile("game.txt");

  if (sudokuFile.is_open()) {
    random_device rd;
    mt19937 gen(rd());

    for (int game = 0; game < numGames - 1; ++game) {
      vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

      solveSudoku(sudoku);
      // 调用中等版本
      generateBlankCellsMedium(sudoku);

      writeSudokuToFile(sudoku, sudokuFile);
      sudokuFile << endl;  // 空一行
    }

    // 处理最后一个局面
    vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));
    solveSudoku(sudoku);
    // 调用中等版本
    generateBlankCellsMedium(sudoku);

    // 写入最后一个局面，但不加入空行
    for (int r = 0; r < SIZE; ++r) {
      for (int c = 0; c < SIZE; ++c) {
        int num = sudoku[r][c];
        if (num != EMPTY) {
          sudokuFile << num << " ";
        } else {
          sudokuFile << EMPTY_CHAR << " ";
        }
      }
      if (r != SIZE - 1) sudokuFile << endl;
    }

    sudokuFile.close();

    cout << "已成功生成中等难度的数独局面并写入文件" << endl;
  } else {
    cout << "无法打开文件" << endl;
  }
}

// 产生带空格的数独——困难，写入game.txt中
void generateSudokuWithBlanks_Hard(int numGames) {
  ofstream sudokuFile("game.txt");

  if (sudokuFile.is_open()) {
    random_device rd;
    mt19937 gen(rd());

    for (int game = 0; game < numGames - 1; ++game) {
      vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

      solveSudoku(sudoku);
      // 调用困难版
      generateBlankCellsHard(sudoku);

      writeSudokuToFile(sudoku, sudokuFile);
      sudokuFile << endl;  // 空一行
    }

    // 处理最后一个局面
    vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));
    solveSudoku(sudoku);
    // 调用困难版
    generateBlankCellsHard(sudoku);

    // 写入最后一个局面，但不加入空行
    for (int r = 0; r < SIZE; ++r) {
      for (int c = 0; c < SIZE; ++c) {
        int num = sudoku[r][c];
        if (num != EMPTY) {
          sudokuFile << num << " ";
        } else {
          sudokuFile << EMPTY_CHAR << " ";
        }
      }
      if (r != SIZE - 1) sudokuFile << endl;
    }

    sudokuFile.close();

    cout << "已成功生成高级难度的数独局面并写入文件" << endl;
  } else {
    cout << "无法打开文件" << endl;
  }
}

int main(int argc, char* argv[]) {
  if (argc < 2) {
    cout << "参数不足" << endl;
    return 0;
  }

  string command = argv[1];

  if (command == "-c") {
    if (argc < 3) {
      cout << "缺少终局数量参数" << endl;
      return 0;
    }

    int numGames = stoi(argv[2]);
    if (numGames < 1 || numGames > 1000000) {
      cout << "终局数量超出范围" << endl;
      return 0;
    }

    generateSudoku(numGames);
  } else if (command == "-s") {
    if (argc < 3) {
      cout << "缺少文件名参数" << endl;
      return 0;
    }

    string inputFile = argv[2];
    string outputFile = "sudoku.txt";

    solveSudokuFromFile(inputFile, outputFile);
  } else if (command == "-n") {
    int numGames = 0;
    int numBlanks = 20;   // -n,默认挖空数量为20
    int numBlanks1 = 40;  // -n-u,默认挖空数量为20

    bool unique = false;

    if (argc < 3) {
      cout << "缺少局面数量参数" << endl;
      return 0;
    }

    numGames = stoi(argv[2]);
    if (numGames < 1 || numGames > 10000) {
      cout << "局面数量超出范围" << endl;
      return 0;
    }

    // 难度选择
    if (argc >= 5 && string(argv[3]) == "-m") {
      int difficultyLevel = stoi(argv[4]);
      if (difficultyLevel == 1) {
        generateSudokuWithBlanks_Easy(numGames);
      } else if (difficultyLevel == 2) {
        generateSudokuWithBlanks_Medium(numGames);
      } else if (difficultyLevel == 3) {
        generateSudokuWithBlanks_Hard(numGames);
      } else {
        cout << "无效的难度级别" << endl;
        return 0;
      }
      return 0;
    }

    if (argc >= 4) {
      if (strcmp(argv[3], "-r") == 0) {
        if (argc < 5) {
          cout << "缺少挖空数量参数" << endl;
          return 0;
        }

        numBlanks = stoi(argv[4]);
        if (numBlanks < 20 || numBlanks > 55) {
          cout << "挖空数量超出范围" << endl;
          return 0;
        }
      } else if (strcmp(argv[3], "-u") == 0) {
        unique = true;
      }
    }

    if (unique) {
      generateUniqueSudokuWithBlanks(numGames, numBlanks1);
    } else {
      generateSudokuWithBlanks(numGames, numBlanks);
    }
  } else {
    cout << "无效的命令" << endl;
  }

  return 0;
}
